package com.arron.algorithm.leetcodetop100.贪心;

public class 跳跃游戏II {


    public int jump(int[] nums) {

        if (nums.length == 1) {
            return 0;
        }

        int minJump = 0;

        for (int i = 0; i < nums.length; ) {

            if (nums[i] + i >= nums.length - 1) {
                minJump++;
                break;
            }


            int maxIndex = 0;
            int max = i+ nums[i];
            for (int j = i+1; j <= i+nums[i]; j++) {
                //如果说有跳得更远得则更新
                if (nums[j]+j > max) {

                    max = nums[j]+j;
                    maxIndex =  j;
                }
            }
            minJump++;
            //如果没有比当前跳得最远的，则跳到当前最远的
            i = maxIndex ==0 ? i+nums[i] : maxIndex ;


        }
        return minJump;
    }

    public static void main(String[] args) {
        跳跃游戏II jump = new 跳跃游戏II();
        int[] nums = {4,1,1,3,1,1,1};
        System.out.println(jump.jump(nums));
    }

}
